Count bit num(BIT)

first
int count_bits(unsigned int data){
int cnt=0;
while(data!=0){
data=data&(data-1);
cnt++;
}
return cnt;
}
data    =    xxxxx10000
data-1 =    xxxxx011111
위와 같이 data-1은  오른쪽에서 최초의 1이 나타나는 시점까지를 1로 바꾸고 최초의 1을 0으로 바꾼다.
따라서 data=data&(data-1)의 코드가 한번 실행 될 때마다 1인 bit가 오른쪽부터 하나씩 꺼진다.
second
static unsigned char byte_bit_count[256];
void initialize_count_bits(){
int cnt, i, data;
for(i=0;i<256;i++){
cnt=0;
data=i;
while(data!=0){
data=data&(data-1);
cnt++;
}
byte_bit_count[i]=cnt;
}
}
int count_bits(unsigned int data){
const unsigned char *byte=(unsigned char *)&data;
return byte_bit_count[byte[0]]+byte_bit_count[byte[1]]+byte_bit_count[byte[2]]+byte_bit_count[byte[3]];
}
위 코드는 미리 lookup table(룩업 테이블)을 생성하고,
이를 이용해서 바이트 별로 켜져 있는 비트수를 세는 소스이다.
third
int count_bits(unsigned int x){
static unsigned int mask[]={0x55555555,0x33333333,0x0F0F0F0F,0x00FF00FF,0x0000FFFF};
int i;
int shift;
for(i=0,shift=1;i<5;i++,shift*=2){
x=(x&mask[i])+((x>>shift)&mask[i]);
}
return x;
}